package Tree;

public class 完全二叉树的节点个数 {
    /**
     * 针对完全二叉树的解法
     * 满二叉树的结点数为：2 ^ depth - 1
     */
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
        for (TreeNode left = root.left; left != null; left = left.left) leftDepth++; // 求左子树深度
        for (TreeNode right = root.right; right != null; right = right.right) rightDepth++; // 求右子树深度
        if (leftDepth == rightDepth) return (2 << leftDepth) - 1; // 注意 (2<<1) 相当于2^2，所以leftDepth初始为0
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
